// Created by WXX on 2021/10/22 20:51
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 求组合数 C(n+m-2, n-1)
class Solution {
public:
    int uniquePaths(int m, int n) {

        int N = n + m - 2, M = min(n - 1, m - 1);
        vector<vector<long long>> C(N + 1, vector<long long>(N + 1));
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= i && j <= M; j++)
                if (!j) C[i][j] = 1;
                else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);

        return C[N][M];
    }
};

int main() {

    cout << Solution().uniquePaths(3, 7) << endl;  // 28

    return 0;
}
